/*
 * @lc app=leetcode.cn id=213 lang=cpp
 *
 * [213] 打家劫舍 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n <= 3){
            // return max value
            sort(nums.begin(), nums.end());
            return nums.back();
        }

        // DP[n][is_robbed] = DP[n-1][not_robbed] + value[n]
        // DP[n][not_robbed] = max(DP[n-1][not_robbed], DP[n-1][is_robbed])

        std::vector< info > DP(n, info());

        int result_1, result_2;
        // first is robbed: 0 1 n-1 can not, 2 ~ n-2 free
        // sum(2 ~ n-2) + value[0]
        DP[2].is_robbed = nums[2];
        // DP[2].not_robbed = 0;
        for (int i=3;i<n-1;i++){
            DP[i].is_robbed = DP[i-1].not_robbed + nums[i]; 
            DP[i].not_robbed = std::max(DP[i-1].is_robbed, DP[i-1].not_robbed);
        }
        // printf("check %d %d %d\n",DP[n-2].not_robbed, DP[n-2].is_robbed, nums[0]);
        result_1 = std::max(DP[n-2].not_robbed, DP[n-2].is_robbed) + nums[0];

        // reset
        // DP = std::vector< info >(n, info());

        // first is not robbed: 0 can not, 1 ~ n-1 free
        // sum(1 ~ n-1) 
        DP[1].is_robbed = nums[1];
        // DP[1].not_robbed = 0;
        for (int i=1;i<n;i++){
            DP[i].is_robbed = DP[i-1].not_robbed + nums[i]; 
            DP[i].not_robbed = std::max(DP[i-1].is_robbed, DP[i-1].not_robbed);
        }
        result_2 = std::max(DP[n-1].not_robbed, DP[n-1].is_robbed);

        return std::max(result_1, result_2);
    }
private:
    struct info{
        int not_robbed;
        int is_robbed;
        info() : not_robbed(0), is_robbed(0){}
        info(int x, int y) : not_robbed(x), is_robbed(y){}
    };
    enum status{
        not_robbed = 0,
        is_robbed = 1
    };
};
// @lc code=end

// [200,3,140,20,10]
int main(){
    vector<int> nums = {200,3,140,20,10};
    Solution test;
    int res = test.rob(nums);
}